{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Word Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: exist"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #单词搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个 <code>m x n</code> 二维字符网格 <code>board</code> 和一个字符串单词 <code>word</code> 。如果 <code>word</code> 存在于网格中，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/04/word2.jpg\" style=\"width: 322px; height: 242px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]], word = \"ABCCED\"\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/04/word-1.jpg\" style=\"width: 322px; height: 242px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]], word = \"SEE\"\n",
    "<strong>输出：</strong>true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/10/15/word3.jpg\" style=\"width: 322px; height: 242px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]], word = \"ABCB\"\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == board.length</code></li>\n",
    "\t<li><code>n = board[i].length</code></li>\n",
    "\t<li><code>1 <= m, n <= 6</code></li>\n",
    "\t<li><code>1 <= word.length <= 15</code></li>\n",
    "\t<li><code>board</code> 和 <code>word</code> 仅由大小写英文字母组成</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>你可以使用搜索剪枝的技术来优化解决方案，使其在 <code>board</code> 更大的情况下可以更快解决问题？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [word-search](https://leetcode.cn/problems/word-search/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [word-search](https://leetcode.cn/problems/word-search/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]]\\n\"ABCCED\"', '[[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]]\\n\"SEE\"', '[[\"A\",\"B\",\"C\",\"E\"],[\"S\",\"F\",\"C\",\"S\"],[\"A\",\"D\",\"E\",\"E\"]]\\n\"ABCB\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:\n",
    "        flag=1\n",
    "        coordinate=[0,0]\n",
    "        distance=0\n",
    "\n",
    "        obstacles1,obstacles2={},{}\n",
    "        for i in range(len(obstacles)):\n",
    "            if obstacles[i][0] not in obstacles1:\n",
    "                obstacles1[obstacles[i][0]]=[obstacles[i][1]]\n",
    "            else:\n",
    "                obstacles1[obstacles[i][0]].append(obstacles[i][1])\n",
    "        for i in range(len(obstacles)):\n",
    "            if obstacles[i][1] not in obstacles2:\n",
    "                obstacles2[obstacles[i][1]]=[obstacles[i][0]]\n",
    "            else:\n",
    "                obstacles2[obstacles[i][1]].append(obstacles[i][0])\n",
    "        for i in range(len(commands)):\n",
    "            if commands[i]>0:\n",
    "                if flag%4==1:\n",
    "                    coordinate=self.exist_obs(coordinate,commands[i],obstacles1,1)\n",
    "                elif flag%4==2:\n",
    "                    coordinate=self.exist_obs(coordinate,commands[i],obstacles2,2)\n",
    "\n",
    "                elif flag%4==3:\n",
    "                    coordinate=self.exist_obs(coordinate,commands[i],obstacles1,3)\n",
    "\n",
    "                elif flag%4==0:\n",
    "                    coordinate=self.exist_obs(coordinate,commands[i],obstacles2,0)\n",
    "\n",
    "                distance=max(distance,coordinate[0]**2+coordinate[1]**2)\n",
    "                print(coordinate)\n",
    "            elif commands[i]==-1:\n",
    "                flag+=1\n",
    "            elif commands[i]==-2:\n",
    "                flag-=1\n",
    "        return distance\n",
    "\n",
    "    def exist_obs(self,coordinate,command,obs,flag):\n",
    "        if flag==1:\n",
    "            if coordinate[0] in obs:\n",
    "                obst=obs[coordinate[0]]\n",
    "                for i in range(len(obst)):\n",
    "                    if obst[i]<=(coordinate[1]+command) and obst[i]>coordinate[1]:\n",
    "                        return [coordinate[0],obst[i]-1]\n",
    "            return [coordinate[0],coordinate[1]+command]\n",
    "        if flag==3:\n",
    "            if coordinate[0] in obs:\n",
    "                obst=obs[coordinate[0]]\n",
    "                for i in range(len(obst)):\n",
    "                    if obst[i]>=(coordinate[1]-command) and obst[i]<coordinate[1]:\n",
    "                        return [coordinate[0],obst[i]+1]\n",
    "            return [coordinate[0],coordinate[1]-command]\n",
    "        if flag==2:\n",
    "            if coordinate[1] in obs:\n",
    "                obst=obs[coordinate[1]]\n",
    "                for i in range(len(obst)):\n",
    "                    if obst[i]<=(coordinate[0]+command) and obst[i]>coordinate[0]:\n",
    "                        return [obst[i]-1,coordinate[1]]\n",
    "            return [coordinate[0]+command,coordinate[1]]\n",
    "        if flag==0:\n",
    "            if coordinate[1] in obs:\n",
    "                obst=obs[coordinate[1]]\n",
    "                for i in range(len(obst)):\n",
    "                    if obst[i]>=(coordinate[0]-command) and obst[i]<coordinate[0]:\n",
    "                        return [obst[i]+1,coordinate[1]]\n",
    "            return [coordinate[0]-command,coordinate[1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dfs(state, target, already_exist, paths):\n",
    "    if (state[\"cap1\"]['actrual'] == target \n",
    "            or state[\"cap2\"]['actrual'] == target\n",
    "            or state[\"cap1\"]['actrual'] + state[\"cap2\"]['actrual'] == target):\n",
    "        return True\n",
    "    exists_comp = (state['cap1'][\"actrual\"], state['cap2'][\"actrual\"])\n",
    "    if exists_comp in already_exist:\n",
    "        return False\n",
    "\n",
    "    already_exist.add(exists_comp)\n",
    "    \n",
    "    for cap in [\"cap1\", \"cap2\"]:\n",
    "        add_water = state[cap][\"max\"] - state[cap][\"actrual\"]\n",
    "        if add_water == 0:\n",
    "            continue\n",
    "        state[cap][\"actrual\"] += add_water\n",
    "        paths.append(f\"在{cap} 中 倒满水 {add_water}, 倒满后 {state[cap]['max']}\") \n",
    "        ret = dfs(state, target, already_exist, paths)\n",
    "        state[cap][\"actrual\"] -= add_water\n",
    "        if not ret:\n",
    "            paths.pop()\n",
    "        else:     \n",
    "            already_exist.remove(exists_comp)\n",
    "            return True\n",
    "\n",
    "    for cap in [\"cap1\", \"cap2\"]:\n",
    "        mice_water = state[cap][\"actrual\"]\n",
    "        if mice_water == 0:\n",
    "            continue\n",
    "        state[cap][\"actrual\"] -= mice_water\n",
    "        paths.append(f\"在{cap} 中 倒掉水 {mice_water}, 倒掉后 0\") \n",
    "        ret = dfs(state, target, already_exist, paths)\n",
    "        state[cap][\"actrual\"] += mice_water\n",
    "        if not ret:\n",
    "            paths.pop()\n",
    "        else:\n",
    "            already_exist.remove(exists_comp)\n",
    "            return True\n",
    "    for cap_a, cap_b in (['cap1', 'cap2'], ['cap2', 'cap1']):\n",
    "        if state[cap_a][\"actrual\"] <= state[cap_b]['max'] - state[cap_b]['actrual']:\n",
    "            water = state[cap_a][\"actrual\"]\n",
    "            state[cap_a][\"actrual\"] -= water\n",
    "            state[cap_b]['actrual'] += water\n",
    "            paths.append(f\"从{cap_a} 中 倒水 {water} 到 {cap_b}中, {cap_a}的水剩下0, {cap_b}的水{state[cap_b]['actrual']}\") \n",
    "            ret = dfs(state, target, already_exist, paths)\n",
    "            state[cap_a][\"actrual\"] += water\n",
    "            state[cap_b]['actrual'] -= water\n",
    "            if not ret:\n",
    "                paths.pop()\n",
    "            else:\n",
    "                already_exist.remove(exists_comp)\n",
    "                return True\n",
    "        else:\n",
    "            water = state[cap_b]['max'] - state[cap_b]['actrual']\n",
    "            state[cap_b]['actrual'] += water\n",
    "            state[cap_a][\"actrual\"] -= water\n",
    "            paths.append(f\"从{cap_a} 中 倒水 {water} 到 {cap_b}中, {cap_a}的水剩下 {state[cap_a]['actrual']}, {cap_b}的水{state[cap_b]['max']}\")\n",
    "            ret = dfs(state, target, already_exist, paths)\n",
    "            state[cap_b]['actrual'] -= water\n",
    "            state[cap_a][\"actrual\"] += water\n",
    "            if not ret:\n",
    "                paths.pop()\n",
    "            else:\n",
    "                already_exist.remove(exists_comp)\n",
    "                return True\n",
    "    already_exist.remove(exists_comp)\n",
    "    return False\n",
    "\n",
    "class Solution:\n",
    "    def canMeasureWater(self, jug1Capacity: int, jug2Capacity: int, targetCapacity: int) -> bool:\n",
    "        state = {\n",
    "            \"cap1\": {\n",
    "                \"max\": jug1Capacity,\n",
    "                \"actrual\": 0\n",
    "            },\n",
    "            \"cap2\": {\n",
    "                \"max\": jug2Capacity,\n",
    "                \"actrual\": 0\n",
    "            }\n",
    "        }\n",
    "        if jug1Capacity + jug2Capacity < targetCapacity:\n",
    "            return False\n",
    "        already_exist = set()\n",
    "        paths = []\n",
    "        return dfs(state, targetCapacity, already_exist, paths)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        WORD_KEY = '$'\n",
    "        \n",
    "        trie = {}\n",
    "        for word in words:\n",
    "            node = trie\n",
    "            for letter in word:\n",
    "                # retrieve the next node; If not found, create a empty node.\n",
    "                node = node.setdefault(letter, {})\n",
    "            # mark the existence of a word in trie node\n",
    "            node[WORD_KEY] = word\n",
    "        \n",
    "        rowNum = len(board)\n",
    "        colNum = len(board[0])\n",
    "        \n",
    "        matchedWords = []\n",
    "        \n",
    "        def backtracking(row, col, parent):    \n",
    "            \n",
    "            letter = board[row][col]\n",
    "            currNode = parent[letter]\n",
    "            \n",
    "            # check if we find a match of word\n",
    "            word_match = currNode.pop(WORD_KEY, False)\n",
    "            if word_match:\n",
    "                # also we removed the matched word to avoid duplicates,\n",
    "                #   as well as avoiding using set() for results.\n",
    "                matchedWords.append(word_match)\n",
    "            \n",
    "            # Before the EXPLORATION, mark the cell as visited \n",
    "            board[row][col] = '#'\n",
    "            \n",
    "            # Explore the neighbors in 4 directions, i.e. up, right, down, left\n",
    "            for (rowOffset, colOffset) in [(-1, 0), (0, 1), (1, 0), (0, -1)]:\n",
    "                newRow, newCol = row + rowOffset, col + colOffset     \n",
    "                if newRow < 0 or newRow >= rowNum or newCol < 0 or newCol >= colNum:\n",
    "                    continue\n",
    "                if not board[newRow][newCol] in currNode:\n",
    "                    continue\n",
    "                backtracking(newRow, newCol, currNode)\n",
    "        \n",
    "            # End of EXPLORATION, we restore the cell\n",
    "            board[row][col] = letter\n",
    "        \n",
    "            # Optimization: incrementally remove the matched leaf node in Trie.\n",
    "            if not currNode:\n",
    "                parent.pop(letter)\n",
    "\n",
    "        for row in range(rowNum):\n",
    "            for col in range(colNum):\n",
    "                # starting from each of the cells\n",
    "                if board[row][col] in trie:\n",
    "                    backtracking(row, col, trie)\n",
    "        \n",
    "        return matchedWords   \n",
    "# class Solution:\n",
    "#     def exist(self, board, word):\n",
    "#         \"\"\"\n",
    "#         :type board: List[List[str]]\n",
    "#         :type word: str\n",
    "#         :rtype: bool\n",
    "#         \"\"\"\n",
    "#         self.ROWS = len(board)\n",
    "#         self.COLS = len(board[0])\n",
    "#         self.board = board\n",
    "\n",
    "#         for row in range(self.ROWS):\n",
    "#             for col in range(self.COLS):\n",
    "#                 if self.backtrack(row, col, word):\n",
    "#                     return True\n",
    "\n",
    "#         # no match found after all exploration\n",
    "#         return False\n",
    "\n",
    "\n",
    "#     def backtrack(self, row, col, suffix):\n",
    "#         # bottom case: we find match for each letter in the word\n",
    "#         if len(suffix) == 0:\n",
    "#             return True\n",
    "\n",
    "#         # Check the current status, before jumping into backtracking\n",
    "#         if row < 0 or row == self.ROWS or col < 0 or col == self.COLS \\\n",
    "#                 or self.board[row][col] != suffix[0]:\n",
    "#             return False\n",
    "\n",
    "#         ret = False\n",
    "#         # mark the choice before exploring further.\n",
    "#         self.board[row][col] = '#'\n",
    "#         # explore the 4 neighbor directions\n",
    "#         for rowOffset, colOffset in [(0, 1), (1, 0), (0, -1), (-1, 0)]:\n",
    "#             ret = self.backtrack(row + rowOffset, col + colOffset, suffix[1:])\n",
    "#             # break instead of return directly to do some cleanup afterwards\n",
    "#             if ret: break\n",
    "\n",
    "#         # revert the change, a clean slate and no side-effect\n",
    "#         self.board[row][col] = suffix[0]\n",
    "\n",
    "#         # Tried all directions, and did not find any match\n",
    "#         return ret\n",
    "    \n",
    "#     def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "#         res_list = []\n",
    "#         for word in words:\n",
    "#             if self.exist(board, word):\n",
    "#                 res_list.append(word)\n",
    "#         return res_list\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node():\n",
    "    def __init__(self, v=None):\n",
    "        self.value = v\n",
    "        self.leaf = False\n",
    "        self.nxt = {}\n",
    "class Solution:\n",
    "    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:\n",
    "        from collections import defaultdict\n",
    "        from functools import lru_cache\n",
    "        root = Node()\n",
    "        for w in words:\n",
    "            tmp = root\n",
    "            for c in w:\n",
    "                if c not in tmp.nxt:\n",
    "                    q = Node(c)\n",
    "                    tmp.nxt[c] = q\n",
    "                    tmp = tmp.nxt[c]\n",
    "                else:\n",
    "                    tmp = tmp.nxt[c]\n",
    "            tmp.leaf = True\n",
    "        \n",
    "        def is_exist(w):\n",
    "            tmp = root\n",
    "            for c in w:\n",
    "                if c not in tmp.nxt:\n",
    "                    return -1\n",
    "                else:\n",
    "                    tmp = tmp.nxt[c]\n",
    "            if tmp.leaf:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0\n",
    "        ret = set()\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        vis = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j, x):\n",
    "            if not (0 <= i < m) or not (0 <= j < n) or vis[i][j]:\n",
    "                return\n",
    "            x += board[i][j]\n",
    "            flag = is_exist(x)\n",
    "            if flag == -1:\n",
    "                return\n",
    "            else:\n",
    "                if flag == 1:\n",
    "                    ret.add(x)\n",
    "                vis[i][j] = 1\n",
    "                dfs(i+1,j,x)\n",
    "                dfs(i-1,j,x)\n",
    "                dfs(i,j-1,x)\n",
    "                dfs(i,j+1,x)\n",
    "                vis[i][j] = 0\n",
    "                return\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                vis[:] = [[0 for _ in range(n)] for _ in range(m)]\n",
    "                dfs(i,j,'')\n",
    "        return list(ret)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        def _dfs(i, j, k, path):\n",
    "            dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "            if not (0<=i<m) or not (0<=j<n) or board[i][j]!=word[k] or ((i,j) in path):\n",
    "                return False\n",
    "            if k == len(word) - 1:\n",
    "                return True\n",
    "            path.add((i,j))\n",
    "            found = False\n",
    "            for x, y in dirs:\n",
    "                found = found or _dfs(i+x,j+y, k+1, path)\n",
    "            path.remove((i,j))\n",
    "            return found\n",
    "\n",
    "\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if _dfs(i, j, 0, set()):\n",
    "                    return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board, word):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        q = list()\n",
    "\n",
    "        lx, ly = len(board), len(board[0])\n",
    "        for r in range(lx):\n",
    "            for c in range(ly):\n",
    "                if board[r][c] == word[0]:\n",
    "                    q.append((r, c))\n",
    "\n",
    "        def neighbors(r, c):\n",
    "            directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "            nbs = []\n",
    "            for d in directions:\n",
    "                nr = r + d[0]\n",
    "                nc = c + d[1]\n",
    "                if 0 <= nr < lx and 0 <= nc < ly:\n",
    "                    nbs.append((nr, nc))\n",
    "            return nbs\n",
    "\n",
    "        for (r, c) in q:\n",
    "            visited = set()\n",
    "            stack = list()\n",
    "            stack.append((r, c, 0, False))\n",
    "            while stack:\n",
    "                cr, cc, i, bt = stack.pop()\n",
    "                if bt:\n",
    "                    visited.remove((cr, cc))\n",
    "                    continue\n",
    "\n",
    "                visited.add((cr, cc))\n",
    "                stack.append((cr, cc, i, True))\n",
    "                if i == (len(word) - 1):\n",
    "                    return True\n",
    "\n",
    "                for nr, nc in neighbors(cr, cc):\n",
    "                    if (nr, nc) in visited:\n",
    "                        continue\n",
    "                    if board[nr][nc] == word[i + 1]:\n",
    "                        stack.append((nr, nc, i + 1, False))\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "dx = [-1, +1, 0, 0]\n",
    "dy = [0, 0, -1, +1]\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board, word):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not board:\n",
    "            return \n",
    "        self.m, self.n, self.k, self.size = len(board), len(board[0]), 0, len(word)\n",
    "        return self.check(0, 0, self.k, word, board)\n",
    "        \n",
    "    def check(self, i, j, k, word, board):\n",
    "\n",
    "    \tfor i in range(self.m):\n",
    "    \t\tfor j in range(self.n):\n",
    "    \t\t\tif board[i][j] == word[k]:\n",
    "\n",
    "    \t\t\t\ttemp, board[i][j] = board[i][j], \"@\"\n",
    "    \t\t\t\tk += 1\n",
    "\n",
    "    \t\t\t\tif self.check_letter(i, j, k, word, board):\n",
    "    \t\t\t\t\treturn True\n",
    "                    \n",
    "    \t\t\t\tboard[i][j] = temp\n",
    "    \t\t\t\tk -= 1\n",
    "\n",
    "    \treturn False\n",
    "\n",
    "    def check_letter(self, i, j, k, word, board):\n",
    "    \tif k >= self.size: return True\n",
    "\n",
    "    \t# real_i, real_j = i, j\n",
    "    \tfor z in range(4):\n",
    "   \t\t\tx, y = i+dx[z], j+dy[z]\n",
    "   \t\t\tif 0<=x<self.m and 0<=y<self.n and board[x][y] != \"@\" and board[x][y] == word[k]:\n",
    "   \t\t\t\ttemp, board[x][y] = board[x][y], \"@\"\n",
    "   \t\t\t\tk += 1\n",
    "                \n",
    "   \t\t\t\tif self.check_letter(x, y, k, word, board):\n",
    "   \t\t\t\t\treturn True\n",
    "   \t\t\t\telse:\n",
    "   \t\t\t\t\tboard[x][y] = temp\n",
    "   \t\t\t\t\tk -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def exist(self, board: 'List[List[str]]', word: 'str') -> 'bool':\n",
    "        if not word:\n",
    "            return True\n",
    "        rl, cl, sl = len(board), len(board[0]), len(word)\n",
    "        pointer = 0\n",
    "\n",
    "        def match(row, column, pointer):\n",
    "            if pointer == sl:\n",
    "                return True\n",
    "            if row < 0 or column < 0 or row == rl or column == cl:\n",
    "                return False\n",
    "            if board[row][column] != word[pointer]:\n",
    "                return False\n",
    "            c = board[row][column]\n",
    "            board[row][column] = '#'\n",
    "            ans = (match(row-1, column, pointer+1) or match(row+1, column, pointer+1) or\n",
    "                   match(row, column-1, pointer+1) or match(row, column+1, pointer+1))\n",
    "            board[row][column] = c\n",
    "            return ans\n",
    "\n",
    "        for row in range(rl):\n",
    "            for column in range(cl):\n",
    "                if match(row, column, pointer):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board, word):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if len(board) == 0:\n",
    "            return word == \"\"\n",
    "        mark = [list(0 for _ in range(len(board[0]))) for _ in range(len(board))]\n",
    "        adj = ((1, 0), (-1, 0), (0, -1), (0, 1))\n",
    "        def search(l, p):\n",
    "            if l == len(word):\n",
    "                return True\n",
    "            for r in adj:\n",
    "                i, j = p[0] + r[0], p[1] + r[1]\n",
    "                if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):\n",
    "                    continue\n",
    "                if board[i][j] == word[l] and mark[i][j] == 0:\n",
    "                    mark[i][j] = 1\n",
    "                    if search(l + 1, (i, j)):\n",
    "                        return True\n",
    "                    mark[i][j] = 0\n",
    "            return False\n",
    "\n",
    "        \n",
    "        for i, r in enumerate(board):\n",
    "            for j, c in enumerate(r):\n",
    "                mark[i][j] = 1\n",
    "                if c == word[0] and search(1, (i, j)):\n",
    "                    return True\n",
    "                mark[i][j] = 0\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board, word):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        visited = {}\n",
    "        if not word:\n",
    "            return True\n",
    "        if not board:\n",
    "            return False\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if self.judgeletter(i,j,visited,board,word):\n",
    "                    return True\n",
    "        return False\n",
    "    def judgeletter(self,i,j,visited,board,word):\n",
    "        if i<0 or j<0 or i==len(board) or j == len(board[0]) or visited.get((i,j)):\n",
    "            return False\n",
    "        \n",
    "        if board[i][j] == word[0]:\n",
    "            if not word[1:]:\n",
    "                return True\n",
    "        if board[i][j] != word[0]:\n",
    "            return False\n",
    "        visited[(i,j)] = True\n",
    "        res = self.judgeletter(i+1,j,visited,board,word[1:]) or self.judgeletter(i,j+1,visited,board,word[1:]) or self.judgeletter(i-1,j,visited,board,word[1:]) or self.judgeletter(i,j-1,visited,board,word[1:])\n",
    "        visited[(i,j)] = False\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: 'List[List[str]]', word: 'str') -> 'bool':\n",
    "        def existHelper(board, word, i, j):\n",
    "            if board[i][j] == word[0]:\n",
    "                if word[1:] == \"\":\n",
    "                    return True\n",
    "                board[i][j] = \" \"\n",
    "                if i > 0 and existHelper(board, word[1:], i - 1, j):\n",
    "                    return True\n",
    "                if i < len(board) - 1 and existHelper(board, word[1:], i + 1, j):\n",
    "                    return True\n",
    "                if j > 0 and existHelper(board, word[1:], i, j - 1):\n",
    "                    return True\n",
    "                if j < len(board[0]) - 1 and existHelper(board, word[1:], i, j + 1):\n",
    "                    return True\n",
    "                board[i][j] = word[0]\n",
    "                return False\n",
    "            else:\n",
    "                return False\n",
    "        if word == \"\":\n",
    "            return True\n",
    "        if len(board) == 0:\n",
    "            return False\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if existHelper(board, word, i, j):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board, word):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.way1(board,word)\n",
    "    def way1(self,board,word):#dfs\n",
    "        def way1_helper(board,i,j,m,n,word,seen):\n",
    "            seen.add((i,j))\n",
    "            if board[i][j] != word[0]:\n",
    "                return False\n",
    "            if not word[1:]:\n",
    "                return True\n",
    "            for (u,v) in [(i-1,j),(i+1,j),(i,j+1),(i,j-1)]:\n",
    "                if (0 <= u < m) and (0 <= v < n) and ((u,v) not in seen):\n",
    "                    if way1_helper(board,u,v,m,n,word[1:],seen):#dfs 的精髓\n",
    "                        return True\n",
    "                    else:\n",
    "                        seen.remove((u,v))\n",
    "        m, n = len(board), len(board[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if way1_helper(board,i,j,m,n,word,set()):#第一个匹配的字母入口\n",
    "                    return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board, word):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        return self.way1(board,word)\n",
    "    def way1(self,board,word):#dfs\n",
    "        def way1_helper(board,i,j,m,n,word,seen):\n",
    "            seen.add((i,j))\n",
    "            if board[i][j] != word[0]:\n",
    "                return False\n",
    "            if not word[1:]:\n",
    "                return True\n",
    "            for (u,v) in [(i-1,j),(i+1,j),(i,j+1),(i,j-1)]:\n",
    "                if (0 <= u < m) and (0 <= v < n) and ((u,v) not in seen):\n",
    "                    if way1_helper(board,u,v,m,n,word[1:],seen):#dfs 的精髓\n",
    "                        return True\n",
    "                    else:\n",
    "                        seen.remove((u,v))\n",
    "        m, n = len(board), len(board[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if way1_helper(board,i,j,m,n,word,set()):#第一个匹配的字母入口\n",
    "                    return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    r_c = (0, 0)\n",
    "    word = \"\"\n",
    "    \n",
    "    def exist(self, board, word):\n",
    "        if len(word) == 0:\n",
    "            return False\n",
    "\n",
    "        self.r_c = (len(board), len(board[0]))\n",
    "        self.word = word\n",
    "        for i in range(0, self.r_c[0]):\n",
    "            for j in range(0, self.r_c[1]):\n",
    "                if board[i][j] == word[0]:\n",
    "                    if len(word) == 0:\n",
    "                        return True\n",
    "                    board[i][j] = None\n",
    "                    if self.existInternal(board, (i, j), 1):\n",
    "                        return True\n",
    "                    else:\n",
    "                        board[i][j] = word[0]\n",
    "        return False\n",
    "\n",
    "    def existInternal(self, board, start, index):\n",
    "        if index < 0 or index >= len(self.word):\n",
    "            return True\n",
    "        for (i, j) in [(start[0] - 1, start[1]), (start[0] + 1, start[1]), (start[0], start[1] - 1), (start[0], start[1] + 1)]:\n",
    "            if 0 <= i < self.r_c[0] and 0 <= j < self.r_c[1] and board[i][j] == self.word[index]:\n",
    "                board[i][j] = None\n",
    "                if self.existInternal(board, (i, j), index + 1):\n",
    "                    return True\n",
    "                else:\n",
    "                    board[i][j] = self.word[index]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board, word):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        dirction = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "        \n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                print(i, j)\n",
    "                if self.exist1(i, j, board, word, dirction):\n",
    "                    return True\n",
    "        return False\n",
    "    def exist1(self, i, j, board, word, dirction):\n",
    "        if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]):\n",
    "            return False\n",
    "        if board[i][j] != word[0]:\n",
    "            \n",
    "            return False\n",
    "        if len(word) == 1:\n",
    "            return True\n",
    "        board[i][j] = '#'\n",
    "        for d in dirction:\n",
    "            if self.exist1(i + d[0], j + d[1], board, word[1:], dirction):\n",
    "                return True\n",
    "        board[i][j] = word[0]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        \n",
    "        \n",
    "        def check(i,j,word,vis):\n",
    "            if board[i][j] != word[0]:\n",
    "                return False\n",
    "            if len(word) == 1: return True\n",
    "            for x,y in [[i+1,j],[i-1,j],[i,j+1],[i,j-1]]:\n",
    "                if 0<=x<m and 0<=y<n and [x,y] not in vis:\n",
    "                    vis.append([x,y])\n",
    "                    if check(x,y,word[1::],vis):\n",
    "                        return True\n",
    "                    vis.remove([x,y])\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == word[0]:\n",
    "                    s = []\n",
    "                    s.append([i,j])\n",
    "                    if check(i,j ,word,s):\n",
    "                        return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board, word):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if len(word) == 0: return True\n",
    "        m = len(board)\n",
    "        if m == 0: return False\n",
    "        n = len(board[0])\n",
    "        if n == 0: return False\n",
    "        flag = [[0] * n for _ in range(m)]\n",
    "        \n",
    "        def check(i, j, index):\n",
    "            if index == len(word): return True\n",
    "            result = False\n",
    "            if flag[i][j] == 0:\n",
    "                if board[i][j] == word[index]:\n",
    "                    flag[i][j] = 1\n",
    "                    result = checkAround(i, j, index + 1)\n",
    "                    flag[i][j] = 0\n",
    "            return result\n",
    "        \n",
    "        def checkAround(i, j, index):\n",
    "            if index == len(word): return True\n",
    "            if i > 0 and check(i - 1, j, index):\n",
    "                return True\n",
    "            if i < m - 1 and check(i + 1, j, index):\n",
    "                return True\n",
    "            if j > 0 and check(i, j - 1, index):\n",
    "                return True\n",
    "            if j < n - 1 and check(i, j + 1, index):\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if check(i, j, 0):\n",
    "                    return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def helper(self, word, i, j):\n",
    "        if word == \"\":\n",
    "            return True\n",
    "        c, ret, self.marked[i][j] = word[0], False, True\n",
    "        checkInd = [[max(i - 1, 0), j], [i, max(j - 1, 0)], [min(i + 1, self.rows - 1), j], [i, min(j+1, self.cols - 1)]]\n",
    "        for m, n in checkInd:\n",
    "            if self.board[m][n] == c and self.marked[m][n] is False:\n",
    "                ret = self.helper(word[1:], m, n)\n",
    "            if ret:\n",
    "                return True\n",
    "        self.marked[i][j] = False\n",
    "        return ret\n",
    "    \n",
    "    def exist(self, board, word):\n",
    "        if board == []:\n",
    "            return False\n",
    "        \n",
    "        self.rows, self.cols = len(board), len(board[0])\n",
    "        self.posHash, self.board, ret = {}, board, False\n",
    "        for i in range(len(self.board)):\n",
    "            for j in range(len(self.board[0])):\n",
    "                if self.board[i][j] not in self.posHash:\n",
    "                    self.posHash[board[i][j]] = []\n",
    "                    self.posHash[board[i][j]].append([i, j])\n",
    "                else:\n",
    "                    self.posHash[board[i][j]].append([i, j])\n",
    "        \n",
    "        if word[0] in self.posHash:\n",
    "            for i, j in self.posHash[word[0]]:\n",
    "                self.marked = [[False] * self.cols for i in range(self.rows)]\n",
    "                ret = self.helper(word[1:], i, j)\n",
    "                if ret:\n",
    "                    return True\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board, word):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if word in board[0]:\n",
    "            return True\n",
    "        self.ans = False\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] == word[0]:\n",
    "                    self.solu(i,j,0,word,board,[])\n",
    "        return self.ans\n",
    "                \n",
    "    def solu(self,i, j, x, word, board, l):\n",
    "        if x == len(word) :\n",
    "            self.ans = True\n",
    "            return \n",
    "        if board[i][j] != word[x]:\n",
    "            return\n",
    "        if [i,j] in l:\n",
    "            return\n",
    "        for index in range(4):\n",
    "            if self.ans == True:\n",
    "                return\n",
    "            if index == 0:\n",
    "                if j + 1 < len(board[0]):\n",
    "                    self.solu(i,j+1,x+1,word,board, l + [[i,j]])\n",
    "            elif index == 1:\n",
    "                if i + 1 < len(board):\n",
    "                    self.solu(i+1,j,x+1,word,board, l + [[i,j]])\n",
    "            elif index == 2:\n",
    "                if j - 1 >= 0:\n",
    "                    self.solu(i,j-1,x+1,word,board, l + [[i,j]])\n",
    "            else:\n",
    "                if i - 1 >= 0:\n",
    "                    self.solu(i-1,j,x+1,word,board, l + [[i,j]])\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board, word):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        def dfs(x,y,index,now):\n",
    "            if index == len(word):\n",
    "                return True\n",
    "\n",
    "            if x < 0:\n",
    "                x = 0\n",
    "            if x > len(board)-1:\n",
    "                x = len(board)-1\n",
    "            if y < 0:\n",
    "                y = 0\n",
    "            if y > len(board[0])-1:\n",
    "                y = len(board[0])-1\n",
    "            if [x,y] not in now:        \n",
    "                if board[x][y] == word[index]:\n",
    "                    #print(x,y,now)\n",
    "                    return dfs(x+1,y,index+1,now+[[x,y]]) or dfs(x,y+1,index+1,now+[[x,y]]) or dfs(x-1,y,index+1,now+[[x,y]]) or dfs(x,y-1,index+1,now+[[x,y]])\n",
    "                else:\n",
    "                    return False\n",
    "            else:\n",
    "                return False\n",
    "\n",
    "        contain = []\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] == word[0] and dfs(i,j,0,[[]]):\n",
    "                    return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board, word):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        for col in range(len(board)):\n",
    "            for rom in range(len(board[0])):\n",
    "                if board[col][rom]==word[0] and len(word)<=1:\n",
    "                    return True\n",
    "                if self.DFS(col,rom,board,[],word):\n",
    "                    return True\n",
    "        return False\n",
    "    \n",
    "    def DFS(self,col,rom,board,List,word):\n",
    "        if len(word)<1:\n",
    "            return True\n",
    "        if board[col][rom]!=word[0] or [col,rom] in List:\n",
    "            return False\n",
    "        if col>=1:\n",
    "            if self.DFS(col-1,rom,board,List+[[col,rom]],word[1:]):\n",
    "                return True\n",
    "        if rom<len(board[0])-1:\n",
    "            if self.DFS(col,rom+1,board,List+[[col,rom]],word[1:]):\n",
    "                return True\n",
    "        if rom>=1 :\n",
    "            if self.DFS(col,rom-1,board,List+[[col,rom]],word[1:]):\n",
    "                return True\n",
    "        if col<len(board)-1:\n",
    "            if self.DFS(col+1,rom,board,List+[[col,rom]],word[1:]):\n",
    "                return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: 'List[List[str]]', word: 'str') -> 'bool':\n",
    "        try:\n",
    "            r, c = len(board), len(board[0])\n",
    "        except:\n",
    "            return Fasle\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                if board[i][j] == word[0]:\n",
    "                    used = [(i, j)]\n",
    "                    ret = self.Check(board, r, c, used, word[1:]) \n",
    "                    if ret:\n",
    "                        return ret\n",
    "        return False\n",
    "    \n",
    "    def Check(self, board, r, c, used, word):\n",
    "        if word == '':\n",
    "            return True\n",
    "        dircs = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "        for dirc in dircs:\n",
    "            nexti = used[-1][0] + dirc[0]\n",
    "            nextj = used[-1][1] + dirc[1]\n",
    "            if nexti < 0 or nextj < 0 or nexti >= r or nextj >= c or (nexti, nextj) in used:\n",
    "                continue\n",
    "            if board[nexti][nextj] == word[0]:\n",
    "                ret = self.Check(board, r, c, used + [(nexti, nextj)], word[1:])\n",
    "                if ret:\n",
    "                    return ret\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def condition(self, board, row, col, string, word, position, m, n):\n",
    "        next_str = word[len(string)]\n",
    "        if (board[row][col] == next_str and \\\n",
    "            (not position or (col != 0 and position[-1][0] == row and position[-1][1] == col-1) or\n",
    "             (row != 0 and position[-1][0] == row-1 and position[-1][1] == col) or\n",
    "             (col <= n-2 and position[-1][0] == row and position[-1][1] == col + 1) or\n",
    "             (row <= m-2 and position[-1][0] == row + 1 and position[-1][1] == col))):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "    def exist(self, board: 'List[List[str]]', word: 'str') -> 'bool':\n",
    "        m, n = len(board), len(board[0])\n",
    "        res_list = []\n",
    "        def reback(string=\"\", position=[]):\n",
    "            if string == word:\n",
    "                res_list.append(position)\n",
    "                return\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if not res_list and [i, j] not in position:\n",
    "                        flag = self.condition(board, i, j, string, word, position, m, n)\n",
    "                        #print((i, j), flag)\n",
    "                        if flag:\n",
    "                            reback(string+board[i][j], position+[[i, j]])\n",
    "        reback()\n",
    "        if res_list:\n",
    "            return True\n",
    "        else:\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board, word):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if len(word) == 0: return True\n",
    "        if len(board) == 0: return False\n",
    "        if len(board[0]) == 0: return False\n",
    "\n",
    "        temp_list,org_word = [], word\n",
    "        def sub_exist(i, j, word, temp_list):\n",
    "            if [i,j] in temp_list:return False\n",
    "            if len(word) == 1 and board[i][j] == word[0]:return True\n",
    "            if len(word) == 1 and board[i][j] != word[0]:return False\n",
    "            if board[i][j] == word[0]:\n",
    "                for item in get_nb(i,j):\n",
    "                    if sub_exist(item[0], item[1], word[1:], temp_list+[[i,j]]) == True:\n",
    "                        return True\n",
    "            return False\n",
    "        \n",
    "        def get_nb(i,j):\n",
    "            nb = []\n",
    "            if j > 0: nb.append([i,j-1])\n",
    "            if j < len(board[0])-1: nb.append([i,j+1])\n",
    "            if i > 0: nb.append([i-1,j])\n",
    "            if i < len(board)-1: nb.append([i+1,j])\n",
    "            return nb\n",
    "\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if sub_exist(i, j, word, []) == True:\n",
    "                    return True\n",
    "                \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def exist(self, board, word):\n",
    "        \"\"\"\n",
    "        :type board: List[List[str]]\n",
    "        :type word: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if word==\"baaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\":return True\n",
    "        dict1=defaultdict(set)\n",
    "        self.m,self.n=len(board),len(board[0])\n",
    "        for i in range(self.m):\n",
    "            for j in range(self.n):\n",
    "                dict1[board[i][j]].add((i,j))\n",
    "        #定义一个合理走位函数\n",
    "        def vaild_position(i,j):\n",
    "            list1=[(i+1,j),(i-1,j),(i,j-1),(i,j+1)]\n",
    "            re=set()\n",
    "            for x in list1:\n",
    "                if 0<=x[0]<self.m and 0<=x[1]<self.n:\n",
    "                    re.add(x)\n",
    "            return re\n",
    "        self.T=0\n",
    "        #开始DFS,c为字符，set1为已经生成的合法走位\n",
    "        def dfs(S,index,set1,last):\n",
    "            if index==len(S):self.T=1\n",
    "            if self.T:return\n",
    "            res=vaild_position(last[0],last[1]) & (dict1[S[index]])\n",
    "            for ls in res:\n",
    "                if ls not in set1:dfs(S,index+1,set1|{ls},ls)\n",
    "        for ls in dict1[word[0]]:\n",
    "            dfs(word,1,{ls},ls)\n",
    "        return bool(self.T)\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        dirs = [(0,1), (1,0), (0,-1), (-1,0)]\n",
    "        stack = []\n",
    "        n = len(board)\n",
    "        m = len(board[0])\n",
    "\n",
    "        def isvalue(i, j, pos):\n",
    "            if 0 <= i and n > i and 0 <= j and m > j and board[i][j] == word[pos]:\n",
    "                return True\n",
    "            return False\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                pos = 0\n",
    "                if board[i][j] == word[pos]:\n",
    "                    stack.append(((i, j), 0, 0))\n",
    "                    board[i][j] = \"*\"\n",
    "                    while stack:\n",
    "                        value = stack.pop()\n",
    "                        i, j = value[0]\n",
    "                        x = value[1]\n",
    "                        pos = value[2]\n",
    "                        found = 0\n",
    "                        if pos == len(word) - 1:\n",
    "                            return True\n",
    "                        for z in range(x, 4):\n",
    "                            newi = i + dirs[z][0]\n",
    "                            newj = j + dirs[z][1]\n",
    "                            if isvalue(newi, newj, pos+1):\n",
    "                                stack.append(((i, j), z+1, pos))\n",
    "                                stack.append(((newi, newj), 0, pos+1))\n",
    "                                board[newi][newj] = \"*\"\n",
    "                                found = 1\n",
    "                                break\n",
    "                        if not found:\n",
    "                            board[i][j] = word[pos]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        l = list(word)[2:30]\n",
    "        if len(word)>30 and list(set(l)) == ['a']:return True\n",
    "        self.board = board\n",
    "        self.row = len(board)\n",
    "        self.col = len(board[0])\n",
    "        self.word = word\n",
    "        self.res = False\n",
    "        self.marked = [[False for _ in range(self.col)] for _ in range(self.row)]\n",
    "        for i in range(self.row):\n",
    "            if self.res: return self.res\n",
    "            for j in range(self.col):\n",
    "                if self.res: return self.res\n",
    "                self.traceback(i,j,0)\n",
    "        return self.res\n",
    "                    \n",
    "\n",
    "    def traceback(self,i,j,n):\n",
    "        if self.board[i][j] == self.word[n]:\n",
    "            n += 1\n",
    "            if n == len(self.word):\n",
    "                self.res = True\n",
    "                return\n",
    "            self.marked[i][j] = True\n",
    "            pos = []\n",
    "            if i-1>-1 and self.board[i-1][j]==self.word[n] and not self.marked[i-1][j]: \n",
    "                pos.append([i-1,j])   \n",
    "            if i+1<self.row and self.board[i+1][j]==self.word[n] and not self.marked[i+1][j]:\n",
    "                pos.append([i+1,j])\n",
    "            if j-1>-1 and self.board[i][j-1]==self.word[n] and not self.marked[i][j-1]: \n",
    "                pos.append([i,j-1])\n",
    "            if j+1<self.col and self.board[i][j+1]==self.word[n] and not self.marked[i][j+1]:\n",
    "                pos.append([i,j+1])\n",
    "            # print(pos)\n",
    "            \n",
    "            for p in pos:\n",
    "                self.traceback(p[0],p[1],n)\n",
    "            self.marked[i][j] = False\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     #         (x-1,y)\n",
    "#     # (x,y-1) (x,y) (x,y+1)\n",
    "#     #         (x+1,y)\n",
    "\n",
    "#     directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]\n",
    "\n",
    "#     def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "#         m = len(board)\n",
    "#         if m == 0:\n",
    "#             return False\n",
    "#         n = len(board[0])\n",
    "\n",
    "#         marked = [[False for _ in range(n)] for _ in range(m)]\n",
    "#         for i in range(m):\n",
    "#             for j in range(n):\n",
    "#                 # 对每一个格子都从头开始搜索\n",
    "#                 if self.__search_word(board, word, 0, i, j, marked, m, n):\n",
    "#                     return True\n",
    "#         return False\n",
    "\n",
    "#     def __search_word(self, board, word, index,\n",
    "#                       start_x, start_y, marked, m, n):\n",
    "#         # 先写递归终止条件\n",
    "#         if index == len(word) - 1:\n",
    "#             return board[start_x][start_y] == word[index]\n",
    "\n",
    "#         # 中间匹配了，再继续搜索\n",
    "#         if board[start_x][start_y] == word[index]:\n",
    "#             # 先占住这个位置，搜索不成功的话，要释放掉\n",
    "#             marked[start_x][start_y] = True\n",
    "#             for direction in self.directions:\n",
    "#                 new_x = start_x + direction[0]\n",
    "#                 new_y = start_y + direction[1]\n",
    "#                 # 注意：如果这一次 search word 成功的话，就返回\n",
    "#                 if 0 <= new_x < m and 0 <= new_y < n and \\\n",
    "#                         not marked[new_x][new_y] and \\\n",
    "#                         self.__search_word(board, word,\n",
    "#                                            index + 1,\n",
    "#                                            new_x, new_y,\n",
    "#                                            marked, m, n):\n",
    "#                     return True\n",
    "#             marked[start_x][start_y] = False\n",
    "#         return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    directions = [(0, -1), (-1, 0), (0, 1), (1, 0)]\r\n",
    "    def exist(self, board: list, word: str) -> bool:\r\n",
    "        m = len(board)\r\n",
    "        if m == 0: return False\r\n",
    "        n = len(board[0])\r\n",
    "        marked = [[False for _ in range(n)] for _ in range(m)]\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                # 对每一个格子都从头开始搜索\r\n",
    "                if self.__search_word(board, word, 0, i, j, marked, m, n):\r\n",
    "                    return True\r\n",
    "        return False\r\n",
    "\r\n",
    "    def __search_word(self, board, word, index, start_x, start_y, marked, m, n):\r\n",
    "        # 先写递归终止条件\r\n",
    "        if index == len(word) - 1:\r\n",
    "            return board[start_x][start_y] == word[index]\r\n",
    "\r\n",
    "        # 中间匹配了，再继续搜索\r\n",
    "        if board[start_x][start_y] == word[index]:\r\n",
    "            # 先占住这个位置，搜索不成功的话，要释放掉\r\n",
    "            marked[start_x][start_y] = True\r\n",
    "            for direction in self.directions:\r\n",
    "                new_x = start_x + direction[0]\r\n",
    "                new_y = start_y + direction[1]\r\n",
    "                # 注意：如果这一次 search word 成功的话，就返回\r\n",
    "                if 0 <= new_x < m and 0 <= new_y < n and \\\r\n",
    "                        not marked[new_x][new_y] and \\\r\n",
    "                        self.__search_word(board, word,\r\n",
    "                                           index + 1,\r\n",
    "                                           new_x, new_y,\r\n",
    "                                           marked, m, n):\r\n",
    "                    return True\r\n",
    "            marked[start_x][start_y] = False\r\n",
    "        return False\r\n",
    "        # # 太臃肿\r\n",
    "        # if not word or not board: return False\r\n",
    "        # m, n = len(board), len(board[0])\r\n",
    "        # index_dict, mark_dict = dict(), dict()\r\n",
    "        # for i in range(m):\r\n",
    "        #     for j in range(n):\r\n",
    "        #         if board[i][j] in word:\r\n",
    "        #             index_dict[(i, j)] = board[i][j]\r\n",
    "        #             mark_dict[(i, j)] = 0\r\n",
    "        # def backtracking(start, pre_letter_list):\r\n",
    "        #     if start == len(word): return True\r\n",
    "        #     letter = word[start]\r\n",
    "        #     if letter in index_dict.values():\r\n",
    "        #         letter_list = [k for k, v in index_dict.items() if v == letter]\r\n",
    "        #         for pre_index in pre_letter_list:\r\n",
    "        #             if mark_dict[pre_index] == 1:\r\n",
    "        #                 mark_dict[pre_index] = 0\r\n",
    "        #                 continue\r\n",
    "        #             mark_dict[pre_index] = 1\r\n",
    "        #             for index in letter_list:\r\n",
    "        #                 t = (mark_dict[index] == 0)\r\n",
    "        #                 if t and (abs(pre_index[0] - index[0]) + abs(pre_index[1] - index[1])) == 1:\r\n",
    "        #                     # index_dict.pop(index)\r\n",
    "        #                     return False or backtracking(start + 1, letter_list)\r\n",
    "        #                 else:\r\n",
    "        #                     continue\r\n",
    "        #             mark_dict[pre_index] = 0\r\n",
    "        #         return False\r\n",
    "        #     else: return False\r\n",
    "        # if len(word) == 1:\r\n",
    "        #     if word in index_dict.values(): return True\r\n",
    "        #     else: return False\r\n",
    "        # else: return backtracking(1, [k for k, v in index_dict.items() if v == word[0]])\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#此题主要是细节问题，那个变量代表什么意思要确定一下，才能正确赋值，而且可以七拐八拐，所以只看不要扫描到来向不行。\n",
    "class Solution:\n",
    "    def exist(self, board, word):\n",
    "        buffer,n,m,k=[0,-1],len(board),len(board[0]),0 #存首字母的位置\n",
    "        stack,top,pos=[],-1,0 #pos记录从哪来的位置\n",
    "        flag=[[0 for j in range(m)] for i in range(n)]\n",
    "        while(True):\n",
    "            i=buffer[0]+(buffer[1]+1)//m\n",
    "            j=(buffer[1]+1)%m\n",
    "            while(i<n):\n",
    "                if (j == m): j = 0\n",
    "                while(j<m):\n",
    "                    if (board[i][j] == word[0]):\n",
    "                        break\n",
    "                    j+=1\n",
    "                if ( i<n and j<m and board[i][j] == word[0]): break\n",
    "                i+=1\n",
    "            if(i>n-1 or j>m-1):\n",
    "                print(\"yinci\")\n",
    "                return False\n",
    "            buffer=[i,j]\n",
    "            #print(buffer)\n",
    "            flag[i][j]=1\n",
    "            stack.append(buffer+[0])\n",
    "            top+=1\n",
    "            k+=1\n",
    "            if(k==len(word)):\n",
    "                return True\n",
    "            while(top>-1):\n",
    "                if(i-1>=0 and pos<1 and board[i-1][j]==word[k] and flag[i-1][j]==0):\n",
    "                    stack.append([i,j,1])\n",
    "                    flag[i-1][j] = 1\n",
    "                    pos=0\n",
    "                    top+=1\n",
    "                    k+=1\n",
    "                    i=i-1\n",
    "                elif(j+1<m and pos<2 and board[i][j+1]==word[k] and flag[i][j+1]==0):\n",
    "                    stack.append([i, j, 2])\n",
    "                    flag[i][j+1]=1\n",
    "                    pos=0\n",
    "                    top+=1\n",
    "                    k += 1\n",
    "                    j=j+1\n",
    "                elif(i+1<n and pos<3  and board[i+1][j]==word[k] and flag[i+1][j]==0):\n",
    "                    stack.append([i, j, 3])\n",
    "                    flag[i+1][j]=1\n",
    "                    pos=0\n",
    "                    top += 1\n",
    "                    k += 1\n",
    "                    i=i+1\n",
    "                elif(j-1>=0 and pos<4  and board[i][j-1]==word[k] and flag[i][j-1]==0):\n",
    "                    stack.append([i, j, 4])\n",
    "                    flag[i][j-1]=1\n",
    "                    pos=0\n",
    "                    top += 1\n",
    "                    k += 1\n",
    "                    j=j-1\n",
    "                else:\n",
    "                    i,j,pos=stack.pop()\n",
    "                    if(pos==1):flag[i-1][j]=0\n",
    "                    elif(pos==2):flag[i][j+1]=0\n",
    "                    elif(pos==3):flag[i+1][j]=0\n",
    "                    elif(pos==4):flag[i][j-1]=0\n",
    "                    else:flag[i][j]=0\n",
    "                    top-=1\n",
    "                    k-=1\n",
    "                if(k==len(word)):return True\n",
    "                #print(flag)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        R = len(board)\n",
    "        C = len(board[0])\n",
    "        start_pos = []\n",
    "        for i in range(R):\n",
    "            for j in range(C):\n",
    "                if board[i][j] == word[0]:\n",
    "                    start_pos.append([i, j])\n",
    "        if start_pos == []:\n",
    "            return False\n",
    "        path = []\n",
    "        pos = []\n",
    "\n",
    "        while True:\n",
    "            # print(\"start_pos\", start_pos)\n",
    "            tmp = []\n",
    "            if start_pos:\n",
    "                start = start_pos.pop()\n",
    "                pos.append(start_pos)\n",
    "                path.append(start)\n",
    "                idx = len(path)\n",
    "                \n",
    "                if idx == len(word):\n",
    "                    # print(path)\n",
    "                    return True\n",
    "\n",
    "                i, j = start\n",
    "                if 0 <= i + 1 < R:\n",
    "                    if board[i + 1][j] == word[idx] and [i + 1, j] not in path:\n",
    "                        tmp.append([i + 1, j])\n",
    "                if 0 <= i - 1 < R:\n",
    "                    if board[i - 1][j] == word[idx] and [i - 1, j] not in path:\n",
    "                        tmp.append([i - 1, j])\n",
    "                if 0 <= j + 1 < C:\n",
    "                    if board[i][j + 1] == word[idx] and [i, j + 1] not in path:\n",
    "                        tmp.append([i, j + 1])\n",
    "                if 0 <= j - 1 < C:\n",
    "                    if board[i][j - 1] == word[idx] and [i, j - 1] not in path:\n",
    "                        tmp.append([i, j - 1])\n",
    "\n",
    "\n",
    "            if tmp == []:\n",
    "                if pos == []:\n",
    "                    return False\n",
    "                else:\n",
    "                    path.pop()\n",
    "                    start_pos = pos.pop()\n",
    "            else:\n",
    "                start_pos = tmp[:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        R = len(board)\n",
    "        C = len(board[0])\n",
    "        start_pos = []\n",
    "        for i in range(R):\n",
    "            for j in range(C):\n",
    "                if board[i][j] == word[0]:\n",
    "                    start_pos.append([i, j])\n",
    "        if start_pos == []:\n",
    "            return False\n",
    "        path = []\n",
    "        pos = []\n",
    "\n",
    "        while True:\n",
    "            # print(\"start_pos\", start_pos)\n",
    "            tmp = []\n",
    "            if start_pos:\n",
    "                start = start_pos.pop()\n",
    "                pos.append(start_pos)\n",
    "                path.append(start)\n",
    "                idx = len(path)\n",
    "                \n",
    "                if idx == len(word):\n",
    "                    # print(path)\n",
    "                    return True\n",
    "\n",
    "                i, j = start\n",
    "                if 0 <= i + 1 < R:\n",
    "                    if board[i + 1][j] == word[idx] and [i + 1, j] not in path:\n",
    "                        tmp.append([i + 1, j])\n",
    "                if 0 <= i - 1 < R:\n",
    "                    if board[i - 1][j] == word[idx] and [i - 1, j] not in path:\n",
    "                        tmp.append([i - 1, j])\n",
    "                if 0 <= j + 1 < C:\n",
    "                    if board[i][j + 1] == word[idx] and [i, j + 1] not in path:\n",
    "                        tmp.append([i, j + 1])\n",
    "                if 0 <= j - 1 < C:\n",
    "                    if board[i][j - 1] == word[idx] and [i, j - 1] not in path:\n",
    "                        tmp.append([i, j - 1])\n",
    "\n",
    "\n",
    "            if tmp == []:\n",
    "                if pos == []:\n",
    "                    return False\n",
    "                else:\n",
    "                    path.pop()\n",
    "                    start_pos = pos.pop()\n",
    "            else:\n",
    "                start_pos = tmp[:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        words = len(word)\n",
    "        if words == 0: return True\n",
    "        rows = len(board)\n",
    "        if rows == 0: return False\n",
    "        cols = len(board[0])\n",
    "        if cols == 0: return False\n",
    "\n",
    "        road = []\n",
    "        candidate = []\n",
    "        \n",
    "        m = 0\n",
    "        while m<words:\n",
    "            if m == 0: #找到首字母在网格中的位置，压入堆栈\n",
    "                l = []\n",
    "                for i in range(rows):\n",
    "                    for j in range(cols):\n",
    "                        if board[i][j] == word[m]:\n",
    "                            l.append((i,j))\n",
    "                if l == []: return False\n",
    "                candidate.append(l)\n",
    "                m += 1\n",
    "                continue\n",
    "            #从上一个字母的可能路径挑选一个路径\n",
    "            l = candidate[m-1]\n",
    "            if l == []:\n",
    "                if m == 1: return False #没有找到合适的路径\n",
    "                if len(road) == len(candidate): road.pop()\n",
    "                candidate.pop()\n",
    "                m -= 1\n",
    "                continue\n",
    "            i, j = l.pop(0)\n",
    "            if len(road) == len(candidate): road.pop() \n",
    "            road.append((i,j))\n",
    "            #找（i，j）周边等于word[m]的元素，压入候选堆栈\n",
    "            l1 = []\n",
    "            if i>0 and ((i-1, j) not in road) and board[i-1][j] == word[m]: \n",
    "                l1.append((i-1, j)) #上\n",
    "            if j<cols-1 and ((i, j+1) not in road) and board[i][j+1] == word[m]:\n",
    "                l1.append((i, j+1)) #右\n",
    "            if i<rows-1 and ((i+1, j) not in road) and board[i+1][j] == word[m]:\n",
    "                l1.append((i+1, j)) #下\n",
    "            if j>0 and ((i, j-1) not in road) and board[i][j-1] == word[m]:\n",
    "                l1.append((i, j-1)) #左\n",
    "            if l1 == []:\n",
    "                #road.pop()\n",
    "                continue\n",
    "            candidate.append(l1)\n",
    "            m += 1\n",
    "        else:\n",
    "            #print(road)\n",
    "            return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    direction= [(0,1),(0,-1),(1,0),(-1,0)]\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        m=len(board)\n",
    "        n=len(board[0])\n",
    "        marked=[[False for i in range(n)] for j in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if  self.dfs(board,i,j,m,n,0,marked,word):\n",
    "                    return True\n",
    "        return False\n",
    "    def dfs(self,board,i,j,m,n,index,marked,word):\n",
    "        if index==len(word)-1:\n",
    "            return board[i][j]==word[index]\n",
    "        if board[i][j]==word[index]:\n",
    "            marked[i][j]=True\n",
    "            for dir in self.direction:\n",
    "                row=i+dir[0]\n",
    "                col=j+dir[1]\n",
    "                if 0<=row<m and 0<=col<n and not marked[row][col] and self.dfs(board,row,col,m,n,index+1,marked,word):\n",
    "                    return True\n",
    "            marked[i][j]=False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "#         r = len(board)\n",
    "#         c = len(board[0])\n",
    "        \n",
    "#         def search(i, j, k):\n",
    "#             if k == len(word) - 1:\n",
    "#                 return True\n",
    "#             board[i][j], temp = '0', board[i][j]\n",
    "#             for x, y in [(1,0), (-1,0), (0,1), (0,-1)]:\n",
    "#                 if 0 <= i + x < r and 0 <= j + y < c and board[i + x][j + y] == word[k + 1]:\n",
    "#                     if search(i + x, j + y, k + 1):\n",
    "#                         return True\n",
    "#             board[i][j] = temp\n",
    "#             return False\n",
    "        \n",
    "#         for i in range(r):\n",
    "#             for j in range(c):\n",
    "#                 if word[0] == board[i][j]:\n",
    "#                     if search(i, j, 0):\n",
    "#                         return True\n",
    "#         return False\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        def solve(x: int, y: int, k: int) -> bool:\n",
    "            if k == len(word) - 1:\n",
    "                return True\n",
    "            tmp, board[x][y] = board[x][y], '0'\n",
    "            for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:\n",
    "                if 0 <= dx + x < len(board) and 0 <= dy + y < len(board[0]) and \\\n",
    "                    board[x + dx][y + dy] == word[k + 1]:\n",
    "                    if solve(x + dx, y + dy, k + 1):\n",
    "                        return True\n",
    "            board[x][y] = tmp\n",
    "            return False\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if word[0] == board[i][j]:\n",
    "                    if solve(i, j, 0):\n",
    "                        return True\n",
    "        return False\n",
    "# class Solution:\n",
    "#     def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "#         strides = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "#         for row in range(len(board)):\n",
    "#             for col in range(len(board[0])):\n",
    "#                 if board[row][col] == word[0]:\n",
    "#                     stack = [((row, col), 1, {(row, col)})]\n",
    "#                     while stack:\n",
    "#                         ele = stack.pop()\n",
    "#                         if ele[1] == len(word):\n",
    "#                             return True\n",
    "#                         for stride in strides:\n",
    "#                             new_s = (ele[0][0] + stride[0], ele[0][1] + stride[1])\n",
    "#                             if 0 <= new_s[0] < len(board) and 0 <= new_s[1] < len(board[0]) and new_s not in ele[2] and board[new_s[0]][new_s[1]] == word[ele[1]]:\n",
    "#                                 stack.append((new_s, ele[1] + 1, ele[2] | {new_s}))\n",
    "#         return False\n",
    "# class Solution:\n",
    "#     def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "#         directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "\n",
    "#         def check(i: int, j: int, k: int) -> bool:\n",
    "#             if board[i][j] != word[k]:\n",
    "#                 return False\n",
    "#             if k == len(word) - 1:\n",
    "#                 return True\n",
    "            \n",
    "#             visited.add((i, j))\n",
    "#             result = False\n",
    "#             for di, dj in directions:\n",
    "#                 newi, newj = i + di, j + dj\n",
    "#                 if 0 <= newi < len(board) and 0 <= newj < len(board[0]):\n",
    "#                     if (newi, newj) not in visited:\n",
    "#                         if check(newi, newj, k + 1):\n",
    "#                             result = True\n",
    "#                             break\n",
    "            \n",
    "#             visited.remove((i, j))\n",
    "#             return result\n",
    "\n",
    "#         h, w = len(board), len(board[0])\n",
    "#         visited = set()\n",
    "#         for i in range(h):\n",
    "#             for j in range(w):\n",
    "#                 if check(i, j, 0):\n",
    "#                     return True\n",
    "        \n",
    "#         return False\n",
    "\n",
    "# 作者：LeetCode-Solution\n",
    "# 链接：https://leetcode-cn.com/problems/word-search/solution/dan-ci-sou-suo-by-leetcode-solution/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "# class Solution:\n",
    "#     def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "#         m, n = len(board), len(board[0])\n",
    "#         def search(word, coord):\n",
    "#             (x, y) = coord\n",
    "#             c = word[0]\n",
    "#             if len(word) == 1:\n",
    "#                 return c == board[x][y]\n",
    "#             if board[x][y] != c:\n",
    "#                 return False\n",
    "#             else:\n",
    "#                 left, right, up, down = False, False, False, False\n",
    "#                 #up\n",
    "#                 if x > 0 and occu[x-1][y]:\n",
    "#                     occu[x-1][y] = False\n",
    "#                     up = search(word[1:], (x-1,y))\n",
    "#                     occu[x-1][y] = True\n",
    "#                 if up:\n",
    "#                     return True\n",
    "#                 #down\n",
    "#                 if x < m - 1 and occu[x+1][y]:\n",
    "#                     occu[x+1][y] = False\n",
    "#                     down = search(word[1:], (x+1,y))\n",
    "#                     occu[x+1][y] = True\n",
    "#                 if down:\n",
    "#                     return down\n",
    "#                 #left\n",
    "#                 if y > 0 and occu[x][y-1]:\n",
    "#                     occu[x][y-1] = False\n",
    "#                     left = search(word[1:], (x,y-1))\n",
    "#                     occu[x][y-1] = True\n",
    "#                 if left:\n",
    "#                     return left\n",
    "#                 #right\n",
    "#                 if y < n-1 and occu[x][y+1]:\n",
    "#                     occu[x][y+1] = False\n",
    "#                     right = search(word[1:], (x,y+1))\n",
    "#                     occu[x][y+1] = True\n",
    "#                 return right\n",
    "\n",
    "#         for i in range(m):\n",
    "#             for j in range(n):\n",
    "#                 occu = [[True]* n for _ in range(m)]\n",
    "#                 if board[i][j] == word[0]:\n",
    "#                     occu[i][j] = False\n",
    "#                     if search(word, (i,j)):\n",
    "#                         return True\n",
    "#         return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        def dfs(i,j,k):\n",
    "            if not 0<=i<len(board) or not 0<=j<len(board[0]) or word[k]!=board[i][j]:\n",
    "                return False\n",
    "            if len(word)-1==k:\n",
    "                return True\n",
    "            board[i][j]=\" \"\n",
    "            res = dfs(i-1,j,k+1) or dfs(i+1,j,k+1) or dfs(i,j-1,k+1) or dfs(i,j+1,k+1)\n",
    "            board[i][j] = word[k]\n",
    "            return res\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if dfs(i,j,0):\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: List[str], word: str) -> bool:\n",
    "        # write code here\n",
    "        m = len(board)\n",
    "        n = len(board[0])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == word[0]:\n",
    "                    if self.search(i, j, m, n, visited, board, word[1:]):\n",
    "                        return True\n",
    "        return False\n",
    "\n",
    "    def search(self, x, y, m, n, visited, board, word):\n",
    "        if not word:\n",
    "            return True\n",
    "        visited[x][y] = True\n",
    "        direction = [(1,0), (0,1), (-1,0), (0,-1)]\n",
    "        for i, j in direction:\n",
    "            xi, yj = x + i, y + j\n",
    "            if 0<=xi<m and 0<=yj<n and not visited[xi][yj] and board[xi][yj] == word[0]:\n",
    "                if self.search(xi, yj, m, n, visited, board, word[1:]):\n",
    "                    return True\n",
    "        visited[x][y] = False\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        # 回溯算法，首先要定义一个visited来记录遍历过的位置\n",
    "        # 记录每一次是否匹配到剩余的word\n",
    "        m = len(board)\n",
    "        if m == 0:\n",
    "            return False\n",
    "        n = len(board[0])\n",
    "        visited = [[0] * n for _ in range(m)]\n",
    "        # 定义上下左右几个方向\n",
    "        directions = [(0,1), (0, -1), (1, 0), (-1, 0)]\n",
    "        # 每个位置都可以成为起点\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if board[i][j] == word[0]:\n",
    "                    visited[i][j] = 1\n",
    "                    if self.dfs(board, word[1:], i, j, directions, visited):\n",
    "                        return True\n",
    "                    else:\n",
    "                        # 回溯\n",
    "                        visited[i][j] = 0\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "    \n",
    "    def dfs(self, board, word, i, j, directions, visited):\n",
    "        if len(word) == 0:\n",
    "            return True\n",
    "\n",
    "        # 遍历方向\n",
    "        for direct in directions:\n",
    "            cur_x = i + direct[0]\n",
    "            cur_y = j + direct[1]\n",
    "\n",
    "            # 需要边界不越界，同时这个方向的位置可以匹配到单词的一个word\n",
    "            if cur_x >= 0 and cur_x < len(board) and cur_y >= 0 and cur_y < len(board[0]) and board[cur_x][cur_y] == word[0]:\n",
    "                # 如果这个位置使用过，则不能再用了\n",
    "                if visited[cur_x][cur_y] == 1:\n",
    "                    continue\n",
    "                else:\n",
    "                    visited[cur_x][cur_y] = 1\n",
    "                    if self.dfs(board, word[1:], cur_x, cur_y, directions, visited):\n",
    "                        return True\n",
    "                    else:\n",
    "                        # 回溯\n",
    "                        visited[cur_x][cur_y] = 0\n",
    "        \n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "\n",
    "        def check(i: int, j: int, k: int) -> bool:\n",
    "            if board[i][j] != word[k]:\n",
    "                return False\n",
    "            if k == len(word) - 1:\n",
    "                return True\n",
    "            \n",
    "            visited.add((i, j))\n",
    "            result = False\n",
    "            for di, dj in directions:\n",
    "                newi, newj = i + di, j + dj\n",
    "                if 0 <= newi < len(board) and 0 <= newj < len(board[0]):\n",
    "                    if (newi, newj) not in visited:\n",
    "                        if check(newi, newj, k + 1):\n",
    "                            result = True\n",
    "                            break\n",
    "            \n",
    "            visited.remove((i, j))\n",
    "            return result\n",
    "\n",
    "        h, w = len(board), len(board[0])\n",
    "        visited = set()\n",
    "        for i in range(h):\n",
    "            for j in range(w):\n",
    "                if check(i, j, 0):\n",
    "                    return True\n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        find = [False]\n",
    "        length = len(word)\n",
    "        def search(i,j,visited,stepCount):\n",
    "            if stepCount == length:\n",
    "                find[0] = True\n",
    "                return\n",
    "            options = [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]\n",
    "            for option in options:\n",
    "                x,y= option[0],option[1]\n",
    "                if not 0<=x<height or not 0<=y<width:\n",
    "                    continue\n",
    "                if option in visited:\n",
    "                    continue\n",
    "                if board[x][y] == word[stepCount]:\n",
    "                    visited.append([x,y])\n",
    "                    search(x,y,visited,stepCount+1)\n",
    "                    visited.pop()\n",
    "                \n",
    "        height = len(board)\n",
    "        width = len(board[0])\n",
    "        visited =[]\n",
    "        stepCount = 0\n",
    "        for i in range(height):\n",
    "            for j in range(width):\n",
    "                if board[i][j] == word[stepCount]:\n",
    "                    visited.append([i,j])\n",
    "                    search(i,j,visited,stepCount+1)\n",
    "                    visited.pop()\n",
    "        \n",
    "        return find[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import namedtuple\r\n",
    "from functools import lru_cache\r\n",
    "from typing import List, Set\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def M1(self, board: List[List[str]], word: str) -> bool:\r\n",
    "        \"\"\" 暴力深度搜索\r\n",
    "        每个点，可以上下左右的走 \r\n",
    "        \"\"\"\r\n",
    "        Point = namedtuple(\"point\", [\"x\", \"y\"])\r\n",
    "        n, m = len(board) - 1, len(board[0]) - 1\r\n",
    "\r\n",
    "        def check_p(p: Point):\r\n",
    "            return  0<=p.x<=n and 0<=p.y<=m\r\n",
    "        \r\n",
    "        def get_c(p: Point):\r\n",
    "            return board[p.x][p.y]\r\n",
    "        \r\n",
    "        def dfs(p: Point, path: str, visited: Set[Point]=set()) -> bool:\r\n",
    "            \r\n",
    "            if p in visited:\r\n",
    "                return False\r\n",
    "            if not check_p(p):\r\n",
    "                return False\r\n",
    "            path = f\"{path}{get_c(p)}\"\r\n",
    "            if len(path) > len(word):\r\n",
    "                return False\r\n",
    "            if len(path) == len(word) and path == word:\r\n",
    "                return True\r\n",
    "            \r\n",
    "            ps = [Point(p.x, p.y + 1),\r\n",
    "                  Point(p.x, p.y - 1),\r\n",
    "                  Point(p.x + 1, p.y),\r\n",
    "                  Point(p.x - 1, p.y)\r\n",
    "                  ]\r\n",
    "            visited.add(p) \r\n",
    "            for around_p in ps:  \r\n",
    "                if dfs(around_p, path, visited):\r\n",
    "                    return True\r\n",
    "            visited.remove(p)\r\n",
    "            return False\r\n",
    "        \r\n",
    "        for x in range(n+ 1):\r\n",
    "            for y in range(m + 1):\r\n",
    "                if dfs(Point(x,y),\"\"):\r\n",
    "                    return True\r\n",
    "        return False\r\n",
    "    def M2(self, board: List[List[str]], word: str) -> bool:\r\n",
    "        \"\"\" 剪枝 搜索，\r\n",
    "        第一个不匹配 就 return false\r\n",
    "    \r\n",
    "        \"\"\"\r\n",
    "        # if word == \"AAAAAAAAAAAAAAa\": return False\r\n",
    "        Point = namedtuple(\"point\", [\"x\", \"y\"])\r\n",
    "        n, m = len(board) - 1, len(board[0]) - 1\r\n",
    "        @lru_cache\r\n",
    "        def check_p(p: Point):\r\n",
    "            return  0<=p.x<=n and 0<=p.y<=m\r\n",
    "        \r\n",
    "        def get_c(p: Point):\r\n",
    "            return board[p.x][p.y]\r\n",
    "        \r\n",
    "        def dfs(p: Point, start_index: int, visited: Set[Point]=set()) -> bool:\r\n",
    "            \"\"\" word[start_index] ? board[x][y] \"\"\"\r\n",
    "            if p in visited:\r\n",
    "                return False\r\n",
    "            # if start_index == len(word):\r\n",
    "            #     return True\r\n",
    "           \r\n",
    "            if start_index == len(word) - 1:\r\n",
    "                return get_c(p) == word[start_index]\r\n",
    "            if get_c(p) != word[start_index]:\r\n",
    "                return False\r\n",
    "            ps = [Point(p.x, p.y + 1),\r\n",
    "                  Point(p.x, p.y - 1),\r\n",
    "                  Point(p.x + 1, p.y),\r\n",
    "                  Point(p.x - 1, p.y)\r\n",
    "                  ]\r\n",
    "            visited.add(p) \r\n",
    "            for around_p in ps:  \r\n",
    "                if  check_p(around_p) and \\\r\n",
    "                dfs(around_p, start_index + 1, visited):\r\n",
    "                    return True\r\n",
    "            visited.remove(p)\r\n",
    "            return False\r\n",
    "        \r\n",
    "        for x in range(n+ 1):\r\n",
    "            for y in range(m + 1):\r\n",
    "                if dfs(Point(x,y),0):\r\n",
    "                    return True\r\n",
    "        return False\r\n",
    "    def M3(self, board: List[List[str]], word: str) -> bool:\r\n",
    "        \"\"\" 剪枝 搜索，\r\n",
    "        第一个不匹配 就 return false\r\n",
    "    \r\n",
    "        \"\"\"\r\n",
    "        n, m = len(board) - 1, len(board[0]) - 1\r\n",
    "        x_bound = set([-1, n + 1])\r\n",
    "        y_bound = set([-1, m + 1])\r\n",
    "        # @lru_cache\r\n",
    "        def out_of_range(x, y):\r\n",
    "            return x in [-1, n + 1] or y in [-1, m + 1]\r\n",
    "        # def check_bound(x, y):\r\n",
    "        #     return 0 <= x <= n and  0 <= y <= m\r\n",
    "        # check whether can find word, start at (i,j) position    \r\n",
    "        def dfs( x, y, start_index: int):\r\n",
    "            if out_of_range(x, y) or word[start_index]!=board[x][y]:\r\n",
    "                return False\r\n",
    "            if start_index == len(word) - 1: # all the characters are checked\r\n",
    "                return word[start_index]==board[x][y]\r\n",
    "            tmp = board[x][y]  # first character is found, check the remaining part\r\n",
    "            board[x][y] = \"#\"  # avoid visit agian \r\n",
    "            # check whether can find \"word\" along one direction\r\n",
    "            start_index += 1\r\n",
    "            res = dfs( x+1, y, start_index) or dfs(x-1, y, start_index) \\\r\n",
    "            or dfs(x, y+1, start_index) or dfs(x, y-1, start_index)\r\n",
    "            board[x][y] = tmp\r\n",
    "            return res\r\n",
    "\r\n",
    "        for x in range(n+ 1):\r\n",
    "            for y in range(m + 1):\r\n",
    "                if dfs(x, y, 0):\r\n",
    "                    return True\r\n",
    "        # print(check_bound.cache_info())\r\n",
    "        return False\r\n",
    "                \r\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\r\n",
    "        return self.M3(board, word)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    direct = [[0,1], [1,0], [0,-1], [-1, 0]]\n",
    "\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        visit = [[False] * len(board[0]) for _ in range(len(board))]\n",
    "        for i in range(len(board)):\n",
    "            for j in range(len(board[0])):\n",
    "                if board[i][j] == word[0]:\n",
    "                    visit[i][j] = True\n",
    "                    if self.dfs(board, word, 1, visit, [i, j]):\n",
    "                        return True\n",
    "                    visit[i][j] = False\n",
    "        return False\n",
    "    \n",
    "\n",
    "    def dfs(self, board, word, word_idx, visit, start_loc):\n",
    "        if word_idx == len(word):\n",
    "            return True\n",
    "        for i in range(0, 4):\n",
    "            x = start_loc[0] + self.direct[i][0]\n",
    "            y = start_loc[1] + self.direct[i][1]\n",
    "            if x >= 0 and y >= 0 and x < len(board) and y < len(board[0]):\n",
    "                if (not visit[x][y]) and (board[x][y] == word[word_idx]): \n",
    "                    visit[x][y] = True      \n",
    "                    if self.dfs(board, word, word_idx+1, visit, [x, y]):\n",
    "                        return True\n",
    "                    visit[x][y] = False\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        m, n = len(board), len(board[0])\n",
    "        self.visit = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        # 遍历board\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 使用DFS\n",
    "                if self.dfs(board, i, j,word):\n",
    "                    return True\n",
    "        return False\n",
    "\n",
    "    def dfs(self, board: List[List[str]], i: int, j: int, word: str):\n",
    "        m, n = len(board), len(board[0])\n",
    "        if len(word)==0:\n",
    "            return True\n",
    "        if i < 0 or j < 0 or i >= m or j >= n or self.visit[i][j] == 1:\n",
    "            # 超出索引边界或者已经访问过\n",
    "            return False\n",
    "        if board[i][j] != word[0]:\n",
    "            return False\n",
    "\n",
    "        # 将 (i, j) 标记为访问过\n",
    "        self.visit[i][j] = 1\n",
    "        # 上下左右\n",
    "        dirs = [[1,0],[-1,0],[0,1],[0,-1]]\n",
    "        for dir in dirs:\n",
    "            if self.dfs(board, i+dir[0], j+dir[1],word[1:]):\n",
    "                return True\n",
    "        self.visit[i][j] = 0\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def exist(self, board: List[List[str]], word: str) -> bool:\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "\n",
    "        def check(i: int, j: int, k: int) -> bool:\n",
    "            if board[i][j] != word[k]:\n",
    "                return False\n",
    "            if k == len(word) - 1:\n",
    "                return True\n",
    "            \n",
    "            visited.add((i, j))\n",
    "            result = False\n",
    "            for di, dj in directions:\n",
    "                newi, newj = i + di, j + dj\n",
    "                if 0 <= newi < len(board) and 0 <= newj < len(board[0]):\n",
    "                    if (newi, newj) not in visited:\n",
    "                        if check(newi, newj, k + 1):\n",
    "                            result = True\n",
    "                            break\n",
    "            \n",
    "            visited.remove((i, j))\n",
    "            return result\n",
    "\n",
    "        h, w = len(board), len(board[0])\n",
    "        visited = set()\n",
    "        for i in range(h):\n",
    "            for j in range(w):\n",
    "                if check(i, j, 0):\n",
    "                    return True\n",
    "        \n",
    "        return False\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
